'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-06-28 09:43:12
'''
'''
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

示例: 

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
'''
from typing import List
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        import sys
        re = sys.maxsize
        i = 0
        j = 0
        if not nums:
            return 0
        tmp = nums[0]
        while j<len(nums):
            # print('haha',tmp)
            if tmp >= s:
                # print(i, j)
                re = min(re, j-i+1)
                tmp-=nums[i]
                i+=1
            else:
                j+=1
                # print(tmp, nums[j])
                if j>=len(nums):
                    break
                tmp += nums[j]
        return re if re != sys.maxsize else 0

if __name__ == "__main__":
    solution = Solution()
    s = 7
    nums = [2,3,1,2,4,3]
    print(solution.minSubArrayLen(s, nums))